#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>


typedef int ElemType;
typedef struct
{
    ElemType *data;
    int size;
}Stable;


void init_stable(Stable &st,int length)
{
    st.size=length;
    st.data=(ElemType*)malloc(sizeof(ElemType)*length);
    //往数组中填入随机数
    srand(time(NULL));
    for(int i=0; i<length; i++)
    {
        st.data[i]=rand()%100;  //生成0~99的随机数
    }
}

//打印数组
void print_stable(Stable st)
{
    for(int i=0; i< st.size ; i++)
    {
        printf("%3d",st.data[i]);
    }
    printf("\n");
}

void swap(int &a,int &b)
{
    int temp=a;
    a=b;
    b=temp;
}

//向下调整算法
void AdjustDown(int* a, int parent,int len)
{
   int dad=parent;      //最后一个父节点下标
   int son=parent*2+1;  //孩子结点
   while(son < len)
   {
       //比较两个孩子结点谁更大
       if(son+1 < len && a[son+1] > a[son]){
           ++son;
       }
       //将最大的孩子结点与父节点比较
       if(son < len && a[son] > a[dad]){
           swap(a[son],a[dad]);
           dad=son;
           son=dad*2+1;
       }else{
           break;
       }
   }
}

//堆排序
void HeapSort(int* a, int len)
{
    //建大堆
    for(int i=len/2-1; i>=0; i--)
    {
        AdjustDown(a,i,len);
    }
    //将最大值交换到末尾
    swap(a[0],a[len-1]);
    for(int i=len-1; i>1; i--)   //i表示数组的长度
    {
        AdjustDown(a,0,i);//此时只有0下标位置不满足大根堆，所以只需调整0位置
        swap(a[0],a[i-1]);
    }
}


int main() {

    Stable st;
    init_stable(st,10);
    print_stable(st);
    HeapSort(st.data,st.size);
    print_stable(st);
    return 0;
}


